package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2019/12/2 14:51
 */
public class SubSequence {
    /**
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     * TODO 还是没能理解，为什么indexOf比自己遍历一遍要快
     */
    @Test
    public void isSubsequence() {
        Assert.assertFalse(isSubsequence("axc", "ahbgdc"));
        Assert.assertFalse(isSubsequence2("axc", "ahbgdc"));
        Assert.assertTrue(isSubsequence("abc", "ahbgdc"));
        Assert.assertTrue(isSubsequence2("abc", "ahbgdc"));
    }

    public boolean isSubsequence(String s, String t) {
        int index = 0;
        for (int i = 0; i < t.length() && index < s.length(); index++) {
            int j = t.indexOf(s.charAt(index), i);
            if (j < 0) {
                break;
            }
            i = j + 1;
        }
        return index >= s.length();
    }

    public boolean isSubsequence2(String s, String t) {
        int index = 0;
        char[] sc = s.toCharArray(), tc = t.toCharArray();
        for (int i = 0; i < t.length() && index < s.length(); i++) {
            if (sc[index] == tc[i]) {
                index++;
            }
        }
        return index == s.length();
    }

    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     */
    @Test
    public void lengthOfLIS() {
        Assert.assertEquals(4, lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
        Assert.assertEquals(5, lengthOfLIS(new int[]{10, 9, 2, 5, 3, 4, 7, 101, 18}));
        Assert.assertEquals(1, lengthOfLIS(new int[]{0}));
    }

    public int lengthOfLIS(int[] nums) {
        int[] res = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    res[i] = Math.max(res[i], res[j] + 1);
                }
            }
            res[i] = Math.max(res[i], 1);
            max = Math.max(res[i], max);
        }
        return max;
    }
}
